/*
https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/solution/shi-suo-you-qu-jian-de-yi-huo-jie-guo-we-uds2/
 */
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution1787 {
    public int minChanges(int[] nums, int k) {
        int[] f=new int[1024];
        Arrays.fill(f,Integer.MAX_VALUE/2);
        f[0]=0;
        for (int i=0;i<k;i++){
            Map<Integer,Integer> map=new HashMap<>();
            int size=0;
            for (int j=i;j<nums.length;j+=k){
                size++;
                map.put(nums[j],map.getOrDefault(nums[j],0)+1);
            }
            int min=Integer.MAX_VALUE;
            for (int j=0;j<1024;j++){
                min=Math.min(f[j],min);
            }
            int[] g=new int[1024];
            Arrays.fill(g,min);
            for (int j=0;j<1024;j++){
                for (Map.Entry<Integer,Integer> entry:map.entrySet()){
                    g[j]=Math.min(g[j],f[j^entry.getKey()]-entry.getValue());
                }
            }
            for (int j=0;j<1024;j++){
                g[j]+=size;
            }
            f=g;
        }
        return f[0];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1787().minChanges(new int[]{3,4,5,2,1,7,3,4,7},3));
    }
}
